package datastructure;

/**
 * @Author leecho
 * @Date: 2021/10/17 10:17
 * @Version 1.0
 */


public class Queen8 {
    /*
    * 思路
    * - 通过一维数组来模拟八皇后中可能存在的解法
    * - 通过总结规律arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])可以进行规则判定
    * - 设定检查规则来判断下一个棋子应该放在哪里
    * 注意
    * - 一定要设定结束递归的判断条件，否则会出现栈溢出
    * */
    int max = 8;
    int[] arr = new int[max];
    int count = 0;
    static int count2 = 0;

    public static void main(String[] args) {
        Queen8 queen8 = new Queen8();
        queen8.check(0);
        System.out.println(queen8.count +" == "+ count2);
    }

    public void printArr(){
        count++;
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public boolean judgeArr(int n){
        count2++;
        for (int i = 0; i < n; i++) {
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])){
                return false;
            }
        }
        return true;
    }

    // 放下每一个棋子
    public void check(int n){
        /*
        * 思路
        * - 这里当放完最后一个棋子以后，n=8是棋子已经放完结束递归
        * - 这里是在for循环中进行递归，所以每一次递归进行了8次，尝试了当放下这个棋子以后，下一排及其后面的所有情况，成功则打印
        * */
        if (n == max){
            printArr();
            return;
        }

        for (int i = 0; i < max; i++) {
            arr[n] = i;
            if (judgeArr(n)){
                check(n+1);
            }
        }
    }
}
